package com.zjw.algorithm;


import java.util.Stack;

/**
 * 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：s = "(()"
 * 输出：2
 * 解释：最长有效括号子串是 "()"
 * 示例 2：
 * <p>
 * 输入：s = ")()())"
 * 输出：4
 * 解释：最长有效括号子串是 "()()"
 * 示例 3：
 * <p>
 * 输入：s = ""
 * 输出：0
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/longest-valid-parentheses
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution5 {

    public static void main(String[] args) {
        System.out.println(new Solution5().longestValidParentheses("()(()"));
    }

    public int longestValidParentheses(String s) {
        return solve(s.toCharArray());
    }

    private int solve(char[] chars) {

        final char LEFT = '(';
        final char RIGHT = ')';

        Stack<Integer> stack = new Stack<>();

        int maxCount = 0;

        stack.push(-1);
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == LEFT) {
                //左括号直接push其下标
                stack.push(i);
            } else {
                //遇到右括号，移除匹配的左括号
                stack.pop();
                if (stack.isEmpty()) {
                    //如果为空，将右括号下标放入，标志这一定是一个新的起点
                    stack.push(i);
                } else {
                    //不为空，这里动态更新最大值，因为在stack中还存在左括号或者空符号，stack.peek标志的是起点
                    //因此这里刷新maxCount
                    maxCount = Math.max(maxCount, i - stack.peek());
                }
            }
        }

        return maxCount;
    }
}
